Baraj pentru lotul olimpic, Bucuresti, mai 1997
Problema 5, Ziua Copilului (Marian Olteanu si Clara Ionescu)
Dificultate: C4-D1

	De ziua copilului, pe stadionul orasului se organizeaza un spectacol
sportiv. In cadrul acestuia, la un moment dat, copiii stau pe doua randuri
fata in fata intr-o ordine oarecare. Li se cere sa alerge unii catre ceilalti
formand din cele doua randuri un singur rand, fara sa schimbe pozitia relativa
a fiecaruia din randul sau initial. De asemenea, copiii trebuie sa-si gaseasca
loc astfel ca in clipa urmatoare din acest rand nou format sa se poata desprinde
toti aceia care pot sa formeze cel mai lung rand posibil, ordonat crescator dupa
inaltime. Nici de date aceasta ei nu au voie sa-si schimbe pozitiile relative
din rand. Ajutati copiii sa formeze, respectand restrictiile, acest rand ordonat
crescator dupa inaltime.
Date de intrare:
	Fisierul de intrare INPUT.TXt are urmatoarea structura:
- pe prima linie sunt scrise doua numere intregi n si m (1<=n,m<=50) reprezentand
numarul de copii din cele doua randuri;
- pe urmatoarea linie sunt scrise inaltimile copiilor (in centimetri) din randul
de lungime n in ordinea in care se afla in momentul in care li se cere sa formeze
un singur rand;
- pe urmatoarea linie sunt scrise inaltimile copiilor (in centimetri) din randul 
de lungime m, de asemenea in ordinea in care se afla in momentul in care li se
cere sa formeze un singur rand.
Date de iesire:
	Fisirul de iesire OUTPUT.TXT va avea urmatorul continut:
- pe prima linie se va scrie lungimea celui mai lung rand posibil;
- pe a doua linie se vor scrie inaltimile copiilor din acest rand;
- pe a treia linie se vor scrie inaltimile copiilor din randul format din cele
doua randuri initiale.
	In cazul in care exista mai mult solutii, se va scrie doar una.
Exemplu:
INPUT.TXT			OUTPUT.TXT
3 3				4
110 130 120			110 120 130 130
180 120 130			110 180 120 130 130 120

Timp maxim de executie/test: 5 secunde
================================
Solutie (Clara Ionescu)
program NoName;
{  uses crt,dos;}
  const MaxN=120;
  type poz=record
             aa,bb:integer;
           end;
  var a,b:array[0..MaxN] of integer;
      c:array[0..MaxN,0..MaxN] of poz;
      af,bf:array[1..MaxN] of boolean;
      n,m,i,j,h,g,cost,sw,max:integer;
      r,m1,s1,s,m2,s2:word;
      p,q:byte;
      tip:char;
      fo:text;

  procedure citeste;
    var f:text;
  begin
    assign(f,'INPUT.TXT');
    reset(f);
    readln(f,n,m);
    for i:=1 to n do
      if not seekeoln(f) then begin read(f,a[i]); af[i]:=false; end;
    readln(f);
    for i:=1 to m do
      if not seekeoln(f) then begin read(f,b[i]); bf[i]:=false; end;
    close(f);
  end;

  procedure Reconstituie(i,j:byte; lit:char);
    var gasit:boolean;
        g,h,x:byte;
  begin
    if lit='a' then af[i]:=true
               else bf[j]:=true;
     begin
           case lit of
                  'a':begin
                        gasit:=false; g:=1;
                        while (not gasit) and (g<i)do
                        begin
                          h:=1;
                          while (not gasit) and (h<j) do
                          begin
                            if (a[i]>=a[g]) and (c[g,h].aa+1=c[i,j].aa)
                            then begin
                                   Reconstituie(g,h,'a');
                                   gasit:=true;
                                 end;
                            if (a[i]>=b[h]) and (c[g,h].bb+1=c[i,j].aa) and (not gasit)
                            then begin
                                   Reconstituie(g,h,'b');
                                   gasit:=true;
                                 end;
                            inc(h);
                          end;
                          inc(g);
                        end;
                        g:=1;
                        while (not gasit) and (g<i) do
                        begin
                          if (a[i]>=a[g]) and (c[g,j].aa+1=c[i,j].aa)
                          then begin
                                 Reconstituie(g,j,'a');
                                 gasit:=true;
                               end;
                          inc(g);
                        end;
                        if not gasit
                        then if a[i]>b[j]
                             then if c[i,j].aa=c[i,j].bb+1
                                  then begin
                                         gasit:=true;
                                         Reconstituie(i,j,'b');
                                       end
                                  else
                             else if a[i]=b[j]
                                  then begin
                                         gasit:=true;
                                         dec(c[i,j].aa);
                                         Reconstituie(i,j,'a');
                                       end;

                      end;
                  'b':begin
                        gasit:=false; g:=1;
                        while (not gasit) and (g<i) do
                        begin
                          h:=1;
                          while (not gasit) and (h<j) do
                          begin
                            if (b[j]>=b[h]) and (c[g,h].bb+1=c[i,j].bb)
                            then begin
                                   Reconstituie(g,h,'b');
                                   gasit:=true;
                                 end;
                            if (b[j]>=a[g]) and (c[g,h].aa+1=c[i,j].bb)
                            then begin
                                   Reconstituie(g,h,'a');
                                   gasit:=true;
                                 end;
                            inc(h);
                          end;
                          inc(g);
                        end;
                        h:=1;
                        while (not gasit) and (h<j) do
                        begin
                          if (b[j]>=b[h]) and (c[i,h].bb+1=c[i,j].bb)
                          then begin
                                 gasit:=true;
                                 Reconstituie(i,h,'b');
                               end;
                          inc(h);
                        end;
                        if not gasit
                        then if a[i]=b[j]
                             then begin
                                    dec(c[i,j].bb);
                                    Reconstituie(i,j,'b');
                                  end
                              else if (b[j]>a[i]) and (c[i,j].bb=c[i,j].aa+1)
                                then begin
                                       gasit:=true;
                                       Reconstituie(i,j,'a');
                                     end;
                      end;
           end;
       end;
    if lit='a'
    then  write(fo,a[i],' ')
         else write(fo,b[j],' ');
  end;

begin
  {clrscr;}
  assign(fo,'OUTPUT.TXT');rewrite(fo);
{  gettime(r,m1,s1,s);
  writeln(m1,' ',s1);}
{  citeste;}
  for i:=1 to n do
    for j:=1 to m do
    begin
      c[i,j].aa:=1; c[i,j].bb:=1;
      for g:=1 to i-1 do
        for h:=1 to j-1 do
        begin
          if (a[i]>=a[g]) and (c[g,h].aa+1>c[i,j].aa)
          then c[i,j].aa:=c[g,h].aa+1;
          if (a[i]>=b[h]) and (c[g,h].bb+1>c[i,j].aa)
          then c[i,j].aa:=c[g,h].bb+1;
          if (b[j]>=b[h]) and (c[g,h].bb+1>c[i,j].bb)
          then c[i,j].bb:=c[g,h].bb+1;
          if (b[j]>=a[g]) and (c[g,h].aa+1>c[i,j].bb)
          then c[i,j].bb:=c[g,h].aa+1;
        end;
      for g:=1 to i-1 do
        if (a[i]>=a[g]) and (c[g,j].aa+1>c[i,j].aa)
        then c[i,j].aa:=c[g,j].aa+1;
      for h:=1 to j-1 do
        if (b[j]>=b[h]) and (c[i,h].bb+1>c[i,j].bb)
        then c[i,j].bb:=c[i,h].bb+1;
      if a[i]>b[j]
      then if c[i,j].aa<c[i,j].bb+1
           then c[i,j].aa:=1+c[i,j].bb
           else
      else if a[i]=b[j]
           then begin inc(c[i,j].aa);inc(c[i,j].bb); end
           else if c[i,j].bb<c[i,j].aa+1
                then c[i,j].bb:=1+c[i,j].aa;
    end;
    max:=1;
  for i:=1 to n do
    for j:=1 to m do
    begin
      if max<c[i,j].aa then begin max:=c[i,j].aa; p:=i; q:=j; tip:='a'; end;
      if max<c[i,j].bb then begin max:=c[i,j].bb; p:=i; q:=j; tip:='b'; end;
    end;
{  gettime(r,m2,s2,s);
  writeln(m2,' ',s2);}
  writeln(fo,max);
  Reconstituie(p,q,tip);
  close(fo);
end.
==============================
	TESTE
Intrare:
test 1:
4 3
1 7 2 9
11 3 4
--------------
test 2:
4 5
1 2 3 4
5 6 7 8 9
--------------
test 3:
10 10
10 11 12 13 14 15 16 17 18 19
1 2 3 4 5 6 7 8 9 10
-----------------
test 4:
4 4
1 3 5 7
2 4 6 8
--------------
test 5:
5 5
1 2 3 15 16 
4 5 6 7 8
-------------------
test 6:
50 50
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 
150 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99
------------------
test 7:
44 43
1 7 2 9 1 7 2 9 1 7 2 9 1 7 2 9 1 7 2 9 1 7 2 9 1 7 2 9 1 7 2 9 1 7 2 9 1 7 2 9 1 7 2 9
11 3 4 11 3 4 11 3 4 11 3 4 11 3 4 11 3 4 11 3 4 11 3 4 11 3 4 11 3 4 11 3 4 11 3 4 11 3 4 11 3 4 4
-----------------
test 8:
50 50
1 9 7 3 11 1 9 7 3 11 1 9 7 3 11 1 9 7 3 11 1 9 7 3 11 1 9 7 3 11 1 9 7 3 11 1 9 7 3 11 1 9 7 3 11 1 9 7 3 11
2 12 2 12 2 12 2 12 2 12 2 12 2 12 2 12 2 12 2 12 2 12 2 12 2 12 2 12 2 12 2 12 2 12 2 12 2 12 2 12 2 12 2 12 2 12 2 12 2 12
====================

Raspunsuri:
test 1:
5
1 3 4 7 9
1 11 3 4 7 2 9
----------------
test 2:
9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
----------------
test 3:
20
1 2 3 4 5 6 7 8 9 10 10 11 12 13 14 15 16 17 18 19
1 2 3 4 5 6 7 8 9 10 10 11 12 13 14 15 16 17 18 19
----------------
test 4:
8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
----------------
test 5:
10
1 2 3 4 5 6 7 8 15 16
1 2 3 4 5 6 7 8 15 16
----------------
test 6:
99
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 150 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99
----------------
test 7:
29
1 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 7 9 9 9 9 9 9 9 9 9 9 9
1 11 3 4 11 3 4 11 3 4 11 3 4 11 3 4 11 3 4 11 3 4 11 3 4 11 3 4 11 3 4 11 3 4 11 3 4 11 3 4 11 3 4 4 7 2 9 1 7 2 9 1 7 2 9 1 7 2 9 1 7 2 9 1 7 2 9 1 7 2 9 1 7 2 9 1 7 2 9 1 7 2 9 1 7 2 9
----------------
test 8:
38
1 2 9 11 11 11 11 11 11 11 11 11 11 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12
1 2 9 7 3 11 1 9 7 3 11 1 9 7 3 11 1 9 7 3 11 1 9 7 3 11 1 9 7 3 11 1 9 7 3 11 1 9 7 3 11 1 9 7 3 11 1 9 7 3 11 12 2 12 2 12 2 12 2 12 2 12 2 12 2 12 2 12 2 12 2 12 2 12 2 12 2 12 2 12 2 12 2 12 2 12 2 12 2 12 2 12 2 12 2 12 2 12 2 12
----------------
